﻿using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace FunctionGraph
{
    struct Region
    {
        public double x0, x1, y0, y1;
        public Region(double x0, double x1, double y0, double y1)
        {
            this.x0 = x0;
            this.x1 = x1;
            this.y0 = y0;
            this.y1 = y1;
        }
        
    }
    class Renderer
    {
        public double Scale;
        public int OffsetX, OffsetY;
        public int Width, Height;
        byte[] bitmap;
        public Renderer(int w, int h)
        {
            bitmap = new byte[w * h];
            this.Width = w;
            this.Height = h;
            this.Scale = 10/256.0;
            this.OffsetX = this.OffsetY = 0;
        }
        public void Draw(Bitmap buffer, IEvaluator[] eval)
        {
            for (int i = 0; i < bitmap.Length; i++)
                bitmap[i] = 3;
            var regions = new Region[1];
            regions[0] = new Region(0, Width, 0, Height);
            RenderGraph(regions, eval);
            Flush(buffer);
        }

        public void Flush(Bitmap buffer)
        {
            if (buffer.Width != Width && buffer.Height != Height)
                throw new ArgumentException("Inconsistent bitmap dimension.");
            var data = buffer.LockBits(new Rectangle(0, 0, Width, Height), System.Drawing.Imaging.ImageLockMode.WriteOnly, System.Drawing.Imaging.PixelFormat.Format32bppRgb);
            unsafe
            {
                int* ptr = (int*)data.Scan0;
                for (int i = 0; i<Height; i++)
                    for (int j = 0; j < Width; j++)
                    {
                        Color c;
                        byte val = bitmap[i * Width + j];
                        if (val == 0)
                            c = Color.White;
                        else if (val == 1)
                            c = Color.Black;
                        else
                            c = Color.FromArgb(230,230,230);
                        ptr[i * Width + j] = c.ToArgb();
                    }
            }
            buffer.UnlockBits(data);
        }

        List<List<Region>> classifiedSubRegions = null;
        List<Region> subRegions = new List<Region>();
        List<Point2D> classifiedPixels = new List<Point2D>();
        private void RenderGraph(Region[] regions, IEvaluator[] evals)
        {
            int cores = evals.Length;
            int[] scan = new int[cores];
            List<Region>[] subpixelRegions = new List<Region>[cores];
            List<Region>[] nextRegions = new List<Region>[cores];
            for (int i = 0; i < cores; i++)
            {
                nextRegions[i] = new List<Region>();
                subpixelRegions[i] = new List<Region>();
            }
            while (regions.Length > 0)
            {
                for (int i = 0; i < cores; i++)
                    nextRegions[i].Clear();
                int kernelSize = Math.Min(cores, regions.Length);
                int blockSize = regions.Length / kernelSize;
                //for (int i = 0; i<kernelSize; i++)
                Parallel.For(0, kernelSize, (int i) =>
                {
                    int i0 = i * blockSize;
                    int i1 = i0 + blockSize;
                    if (i == kernelSize - 1)
                        i1 = regions.Length;
                    for (int j = i0; j < i1; j++)
                    {
                        var r = regions[j];
                        var rs = evals[i].Evaluate(RangeToIntervalX(r), RangeToIntervalY(r));
                        if (rs.Intervals.Count == 0 || rs.Intervals.Count == 1 && rs.Intervals[0].Def1 == false)
                        {
                            ClearPixels(bitmap, r);
                        }
                        else if (rs.Intervals.Count == 1 && rs.Intervals[0].Def0 && (IsFF(rs) || IsTT(rs)))
                        {
                            if (IsFF(rs))
                            {
                                ClearPixels(bitmap, r);
                            }
                            else
                                SetPixels(bitmap, r);
                        }
                        else if (r.x1 - r.x0 > 1.0)
                        {
                            SplitRegion(r, nextRegions[i]);
                        }
                        else
                        {
                            SplitRegion(new Region(r.x0, r.x1, r.y0, r.y1), subpixelRegions[i]);
                        }
                    }
                });
                for (int i = 0; i < kernelSize; i++)
                    scan[i] = nextRegions[i].Count;
                int sum = 0;
                for (int i = 0; i < kernelSize; i++)
                {
                    var s = scan[i];
                    scan[i] = sum;
                    sum += s;
                }
                regions = new Region[sum];
                for (int i = 0; i < kernelSize; i++)
                    for (int j = 0; j < nextRegions[i].Count; j++)
                        regions[scan[i] + j] = nextRegions[i][j];
            }
            int totalRegions = 0;
            foreach (var list in subpixelRegions)
            {
                totalRegions += list.Count;
            }
            subRegions.Capacity = totalRegions;
            foreach (var list in subpixelRegions)
            {
                subRegions.AddRange(list);
            }
        }

        private Interval RangeToIntervalY(Region r)
        {
            return new Interval((OffsetY + Height - r.y1) * Scale + 1e-7, (OffsetY + Height - r.y0) * Scale + 1e-7);
        }

        private Interval RangeToIntervalX(Region r)
        {
            return new Interval((OffsetX + r.x0) * Scale + 1e-7, (OffsetX + r.x1) * Scale + 1e-7);
        }

        private bool IsTT(IntervalSet rs)
        {
            return !IsFF(rs) && (rs.Intervals[0].Val0 > 0 || rs.Intervals[0].Val1 < 0);
        }

        private bool IsFF(IntervalSet rs)
        {
            return rs.Intervals[0].Val0 == rs.Intervals[0].Val1 && rs.Intervals[0].Val0 == 0;
        }

        public bool Finished
        {
            get
            {
                return subRegions.Count == 0 || (classifiedSubRegions!=null && classifiedSubRegions.Count==0);
            }
        }

        public bool Refine(IEvaluator[] evals, CancellationToken cancellation, int steps=1)
        {
            try
            {
                if (classifiedSubRegions == null)
                    ClassifySubRegions();

                int cores = evals.Length;
                List<List<Region>> nextRegions = new List<List<Region>>(classifiedSubRegions.Count);
                for (int i = 0; i < classifiedSubRegions.Count; i++)
                {
                    nextRegions.Add(new List<Region>());
                }
                while (classifiedSubRegions.Count > 0 && steps > 0)
                {
                    steps--;
                    int kernelSize = Math.Min(cores, classifiedSubRegions.Count);
                    int blockSize = classifiedSubRegions.Count / kernelSize;
                    bool oom = false;
                    Parallel.For(0, kernelSize, (i, ls) =>
                    {
                        if (cancellation.IsCancellationRequested)
                            ls.Break();
                        for (int j = blockSize * i; j < blockSize * (i + 1); j++)
                        {
                            try
                            {
                                if (cancellation.IsCancellationRequested)
                                    break;
                                nextRegions[j].Clear();
                                var pix = classifiedPixels[j];
                                if (pix.x == 257 && (pix.y == 255 || pix.y == 256))
                                    Console.WriteLine("break");
                                for (int k = 0; k < classifiedSubRegions[j].Count; k++)
                                {
                                    var r = classifiedSubRegions[j][k];

                                    var rs = evals[i].Evaluate(RangeToIntervalX(r), RangeToIntervalY(r));
                                    if (rs.Intervals.Count == 1 && rs.Intervals[0].Val0 == rs.Intervals[0].Val1 &&
                                        rs.Intervals[0].Def0)
                                    {
                                        if (rs.Intervals[0].Val0 == 1)
                                        {
                                            SetSubPixel(bitmap, r);
                                            nextRegions[j].Clear();
                                            break;
                                        }
                                        else
                                        {
                                            if (k == classifiedSubRegions[j].Count - 1)
                                                ClearSubPixel(bitmap, r);
                                        }
                                    }
                                    else if (rs.Intervals.Count == 0 || rs.Intervals.Count == 1 && rs.Intervals[0].Def0 == false && rs.Intervals[0].Def1 == false)
                                    {
                                        if (k == classifiedSubRegions[j].Count - 1)
                                            ClearSubPixel(bitmap, r);
                                    }
                                    else if (evals[i].ContainsSolution(RangeToIntervalX(r), RangeToIntervalY(r))
                                        //&& (int)r.y1 == pix.y && (int)r.x1 == pix.x && r.x0>pix.x && r.y0>pix.y
                                        )
                                    {
                                        SetSubPixel(bitmap, r);
                                        nextRegions[j].Clear();
                                        break;
                                    }
                                    else if (r.x1 - r.x0 > (rs.Intervals[0].Def0 ? (1/512.0) : 1 / 64.0))
                                    {
                                        SplitRegion(r, nextRegions[j]);
                                    }
                                    else
                                    {
                                        if (!rs.Intervals[0].Def0)
                                            ClearSubPixel(bitmap, r);
                                        else
                                            Console.WriteLine("break");
                                        nextRegions[j].Clear();
                                    }
                                }
                                if (nextRegions[j].Count == 0)
                                    classifiedSubRegions[j] = null;
                                else
                                    classifiedSubRegions[j] = nextRegions[j];

                            }
                            catch (OutOfMemoryException)
                            {
                                oom = true;
                                classifiedSubRegions[j] = null;
                                ls.Break();
                            }
                        }
                    });
                    if (oom || cancellation.IsCancellationRequested)
                    {
                        classifiedPixels.Clear();
                        classifiedSubRegions.Clear();
                        return false;
                    }
                    // compact classified regions
                    List<List<Region>> nregions = new List<List<Region>>();
                    List<Point2D> npixels = new List<Point2D>();
                    int totalCount = 0;
                    for (int i = 0; i < classifiedSubRegions.Count; i++)
                        if (classifiedSubRegions[i] != null)
                        {
                            totalCount += classifiedSubRegions[i].Count;
                            nregions.Add(classifiedSubRegions[i]);
                            npixels.Add(classifiedPixels[i]);
                        }
                    //if (totalCount > (1 << 22))
                    //{
                    //    classifiedSubRegions.Clear();
                    //    classifiedPixels.Clear();
                    //}
                    //else
                    {
                        classifiedSubRegions = nregions;
                        classifiedPixels = npixels;
                    }
                }
                return classifiedSubRegions.Count > 0;
            }
            catch (OutOfMemoryException)
            {
                if (classifiedPixels != null)
                    classifiedPixels.Clear();
                if (classifiedSubRegions != null)
                    classifiedSubRegions.Clear();
                return false;
            }
        }

        private void ClassifySubRegions()
        {
            subRegions.Sort(new Comparison<Region>((r1, r2) =>
            {
                int x1 = (int)r1.x0;
                int y1 = (int)r1.y0;
                int x2 = (int)r2.x0;
                int y2 = (int)r2.y0;
                return x1 < x2 ? -1 : x1 > x2 ? 1 : y1 < y2 ? -1 : y1 > y2 ? 1 : 0;
            }));
            int x0 = -1;
            int y0 = -1;
            classifiedSubRegions = new List<List<Region>>();
            classifiedPixels = new List<Point2D>();
            for (int i = 0; i < subRegions.Count; i++)
            {
                int x = (int)subRegions[i].x0;
                int y = (int)subRegions[i].y0;
                if (x != x0 || y != y0)
                {
                    classifiedSubRegions.Add(new List<Region>());
                    classifiedPixels.Add(new Point2D() { x = x, y = y });
                    x0 = x;
                    y0 = y;
                }
                classifiedSubRegions[classifiedSubRegions.Count - 1].Add(subRegions[i]);
            }
        }

        private void SplitRegion(Region r, List<Region> regions)
        {
            double midX = (r.x0 + r.x1) / 2;
            double midY = (r.y0 + r.y1) / 2;
            regions.Add(new Region(r.x0, midX, r.y0, midY));
            regions.Add(new Region(midX, r.x1, r.y0, midY));
            regions.Add(new Region(midX, r.x1, midY, r.y1));
            regions.Add(new Region(r.x0, midX, midY, r.y1));
        }

        private void SetPixels(byte[] bitmap, Region r)
        {
            for (int y = (int)r.y0; y < (int)r.y1; y++)
            {
                for (int x = (int)r.x0; x < (int)r.x1; x++)
                {
                    bitmap[y * Width + x] = 1;
                }
            }
        }

        private void ClearPixels(byte[] bitmap, Region r)
        {
            for (int y = (int)r.y0; y < (int)r.y1; y++)
            {
                for (int x = (int)r.x0; x < (int)r.x1; x++)
                {
                    bitmap[y * Width + x] = 0;
                }
            }
        }

        private void SetSubPixel(byte[] bitmap, Region r)
        {
            int y0 = (int)r.y0;
            int x0 = (int)r.x0;
            bitmap[y0 * Width + x0] = 1;
        }

        private void ClearSubPixel(byte[] bitmap, Region r)
        {
            int y0 = (int)r.y0;
            int x0 = (int)r.x0;
            bitmap[y0 * Width + x0] = 0;
        }
    }

    struct Point2D
    {
        public int x, y;
        public override int GetHashCode()
        {
 	         return x^y;
        }
    }
}
